#ifndef __KDTreeH__
#define __KDTreeH__

#include <vector>
#include "Triangle.h"
#include "sphere.h"
#include "SceneTree.h"
#define SPLITX 0
#define SPLITY 1
#define SPLITZ 2

class SceneParser;
struct KDNode
{
	std::vector<Triangle *> *pvpTriangles;
	int splitXYZ;					// x=0,y=1,z=2;
	float splitValue;
	KDNode *pLeftNode,*pRightNode;	// left<=splitValue
	AABB aabb;
	KDNode(){
		pLeftNode = pRightNode = NULL;
		pvpTriangles = new std::vector<Triangle*>;}
	~KDNode() { if (pvpTriangles) delete pvpTriangles; }
	void addTriangle(Triangle *pTriangle){
		pvpTriangles->push_back(pTriangle);
		aabb.updateByVec3f(pTriangle->getV0());
		aabb.updateByVec3f(pTriangle->getV1());
		aabb.updateByVec3f(pTriangle->getV2());
	}
	bool intersect(const Ray *pRay,Hit *pHit,float tmin,float tmax) const{
		float minT = FLT_MAX;
		Hit hit;
		for (size_t i=0; i < pvpTriangles->size(); i++){
			if ( (*pvpTriangles)[i]->intersect(pRay,pHit,tmin,tmax) )
				if (pHit->getT()>tmin && pHit->getT()<tmax && pHit->getT()<minT)
				{
					minT = pHit->getT();
					hit = *pHit;
				}
		}
		if ( minT >tmin && minT < tmax){
			*pHit = hit;
			return true;
		}
		return false;
	}
	bool intersectShadowRay(const Ray *pRay,float tmin,float tmax) const{
		for (size_t i=0; i < pvpTriangles->size(); i++){
			if ( (*pvpTriangles)[i]->intersectShadowRay(pRay,tmin,tmax) )
				return true;
		}
		return false;
	}
};

class KDTree : public SceneTree
{
public:
	KDTree(int maxDepth=6, size_t minTriangles = 10);
	virtual ~KDTree();
	std::string getName() { return "kd-tree"; }
	size_t getFaceAmout() { return m_pRoot->pvpTriangles->size(); }
	void addTriangle(Triangle *pTriangle);
	void addSphere(Sphere *pSphere);
	void buildTree();
	bool intersect(const Ray *pRay, Hit *pHit, float tmin, float tmax);
	bool intersectShadowRay(const Ray *pRay, float tmin, float tmax);
	void debugMessage();
private:
	// help methods
	inline void trySplitValue(KDNode *&pLeftNode,KDNode *&pRightNode,KDNode *&pNode,
		float &splitValue,float &minSAH,int xyz);
	void deleteKDNode(KDNode *pNode);
	void createNode(KDNode *pNode, int depth, int currXYZ);
	bool searchNode(const KDNode *pNode, const Ray *pRay, 
		Hit *pHit, float tmin, float tmax, int depth);
private:
	int m_maxDepth;
	size_t m_minTriangles;
	KDNode *m_pRoot;
	std::vector<Sphere*> m_sphereList;
};

#endif